{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Average Waiting Time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: averageWaitingTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #平均等待时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个餐厅，只有一位厨师。你有一个顾客数组 <code>customers</code> ，其中 <code>customers[i] = [arrival<sub>i</sub>, time<sub>i</sub>]</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arrival<sub>i</sub></code> 是第 <code>i</code> 位顾客到达的时间，到达时间按 <strong>非递减</strong> 顺序排列。</li>\n",
    "\t<li><code>time<sub>i</sub></code> 是给第 <code>i</code> 位顾客做菜需要的时间。</li>\n",
    "</ul>\n",
    "\n",
    "<p>当一位顾客到达时，他将他的订单给厨师，厨师一旦空闲的时候就开始做这位顾客的菜。每位顾客会一直等待到厨师完成他的订单。厨师同时只能做一个人的订单。厨师会严格按照 <strong>订单给他的顺序</strong> 做菜。</p>\n",
    "\n",
    "<p>请你返回所有顾客需要等待的 <strong>平均 </strong>时间。与标准答案误差在 <code>10<sup>-5</sup></code> 范围以内，都视为正确结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>customers = [[1,2],[2,5],[4,3]]\n",
    "<b>输出：</b>5.00000\n",
    "<strong>解释：\n",
    "</strong>1) 第一位顾客在时刻 1 到达，厨师拿到他的订单并在时刻 1 立马开始做菜，并在时刻 3 完成，第一位顾客等待时间为 3 - 1 = 2 。\n",
    "2) 第二位顾客在时刻 2 到达，厨师在时刻 3 开始为他做菜，并在时刻 8 完成，第二位顾客等待时间为 8 - 2 = 6 。\n",
    "3) 第三位顾客在时刻 4 到达，厨师在时刻 8 开始为他做菜，并在时刻 11 完成，第三位顾客等待时间为 11 - 4 = 7 。\n",
    "平均等待时间为 (2 + 6 + 7) / 3 = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>customers = [[5,2],[5,4],[10,3],[20,1]]\n",
    "<b>输出：</b>3.25000\n",
    "<strong>解释：\n",
    "</strong>1) 第一位顾客在时刻 5 到达，厨师拿到他的订单并在时刻 5 立马开始做菜，并在时刻 7 完成，第一位顾客等待时间为 7 - 5 = 2 。\n",
    "2) 第二位顾客在时刻 5 到达，厨师在时刻 7 开始为他做菜，并在时刻 11 完成，第二位顾客等待时间为 11 - 5 = 6 。\n",
    "3) 第三位顾客在时刻 10 到达，厨师在时刻 11 开始为他做菜，并在时刻 14 完成，第三位顾客等待时间为 14 - 10 = 4 。\n",
    "4) 第四位顾客在时刻 20 到达，厨师拿到他的订单并在时刻 20 立马开始做菜，并在时刻 21 完成，第四位顾客等待时间为 21 - 20 = 1 。\n",
    "平均等待时间为 (2 + 6 + 4 + 1) / 4 = 3.25 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= customers.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= arrival<sub>i</sub>, time<sub>i</sub> <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>arrival<sub>i </sub><= arrival<sub>i+1</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [average-waiting-time](https://leetcode.cn/problems/average-waiting-time/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [average-waiting-time](https://leetcode.cn/problems/average-waiting-time/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,5],[4,3]]', '[[5,2],[5,4],[10,3],[20,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        sum1,cur_time=0,0\n",
    "        for ele in customers:\n",
    "            cur_time = max(cur_time,ele[0])+ele[1]\n",
    "            sum1+=cur_time-ele[0]\n",
    "        return sum1/len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        now, total = 0, 0\n",
    "        for arrival, time in customers:\n",
    "            if now < arrival:\n",
    "                now = arrival\n",
    "            now += time\n",
    "            total += now - arrival\n",
    "        return total / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        start,wait=0,0\n",
    "        n=len(customers)\n",
    "        for a,t in customers:\n",
    "            if a>=start:\n",
    "                wait=wait+t\n",
    "                start=a+t\n",
    "            else:\n",
    "                wait=wait+start-a+t\n",
    "                start=start+t\n",
    "        return wait/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        wait_sum, a = 0, 0\n",
    "        for arrive, cost in customers:\n",
    "            if a <= arrive:\n",
    "                a = arrive\n",
    "                a = arrive + cost\n",
    "                wait_sum = wait_sum + cost\n",
    "            else:\n",
    "                a = a + cost\n",
    "                wait_sum = wait_sum + (a-arrive)\n",
    "        return wait_sum/len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        cur, wait = 0., 0.\n",
    "        for x, y in customers:\n",
    "            cur = max(cur, x) + y\n",
    "            wait += cur - x\n",
    "        return wait / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        start = 0\n",
    "\n",
    "        waits = 0\n",
    "        for a, t in customers:\n",
    "            if start < a:\n",
    "                waits += t\n",
    "                start = a + t\n",
    "            else:\n",
    "                waits += (start + t) - a\n",
    "                start = start + t\n",
    "\n",
    "        return waits / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        suml,cur_time=0,0\n",
    "        for ele in customers:\n",
    "            cur_time=max(cur_time,ele[0])+ele[1]\n",
    "            suml+=cur_time-ele[0]\n",
    "        return suml/len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        wait_sum = 0\n",
    "        chef = 0    #可以做菜的时刻\n",
    "        for arrive, cost in customers:\n",
    "            if chef <= arrive:\n",
    "                chef = arrive\n",
    "                chef += cost\n",
    "                wait_sum += cost\n",
    "            else:\n",
    "                chef += cost\n",
    "                wait_sum += (chef - arrive)\n",
    "        return wait_sum / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        total = 0\n",
    "        current = 0\n",
    "        for c in customers:\n",
    "            if current < c[0]:\n",
    "                total += c[1]\n",
    "                current = c[0]+ c[1]\n",
    "            else:\n",
    "                total += c[1] + current - c[0]\n",
    "                current += c[1]\n",
    "        return total / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        ans=0\n",
    "        finishtime=0\n",
    "        i=0\n",
    "        while i<len(customers):\n",
    "            finishtime=max(customers[i][0],finishtime)\n",
    "            ans+=finishtime-customers[i][0]+customers[i][1]\n",
    "            finishtime+=customers[i][1]\n",
    "            i+=1\n",
    "        return ans/len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        ans = 0\n",
    "        start = customers[0][0]\n",
    "        for arrival, t in customers:\n",
    "            if arrival >= start:\n",
    "                start = arrival + t \n",
    "                ans += t\n",
    "            else:\n",
    "                start += t \n",
    "                ans += start - arrival\n",
    "        return ans / n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        end_time=1\n",
    "        wait=0\n",
    "        for start,duration in customers:\n",
    "            if start<end_time:\n",
    "                wait+=end_time-start\n",
    "            else:\n",
    "                end_time=start\n",
    "            end_time+=duration\n",
    "            wait+=duration\n",
    "        return wait/len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        curr_end = sum(customers[0])\n",
    "        sums = customers[0][1]\n",
    "        for s, c in customers[1:]:\n",
    "            if s >= curr_end:\n",
    "                curr_end = (s + c)\n",
    "                sums += c\n",
    "            elif s < curr_end:\n",
    "                wait_time = curr_end - s + c\n",
    "                curr_end += c\n",
    "                sums += wait_time\n",
    "        return sums / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        times = 0\n",
    "        cur = 1\n",
    "        for a, t in customers:\n",
    "            times += max(0, cur - a) + t\n",
    "            cur = max(cur, a) + t\n",
    "        return times / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        res=0\n",
    "        t=0\n",
    "        n=len(customers)\n",
    "        for x,y in customers:\n",
    "            if t<=x:\n",
    "                t=x\n",
    "            res+=(t-x+y)\n",
    "            t+=y\n",
    "        return res/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for a, t in customers:\n",
    "            cur = max(cur, a) + t\n",
    "            res += cur - a\n",
    "        return res / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        dish_time = 0 #做完菜的时间\n",
    "        wait_time = 0 # 顾客等待时间之和\n",
    "    \n",
    "        for (arrive,make) in customers:\n",
    "            if arrive>=dish_time:\n",
    "                dish_time = arrive\n",
    "            dish_time = dish_time + make\n",
    "            wait_time += dish_time-arrive\n",
    "            \n",
    "        return wait_time/len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        time = 0\n",
    "        cnt = 0\n",
    "        for start, duration in customers:\n",
    "            time = max(time - start, 0) + start + duration\n",
    "            cnt += time - start\n",
    "        return cnt / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        end = 0 \n",
    "        ans = 0 \n",
    "        for a, t in customers:\n",
    "            if a < end:\n",
    "                ans += end-a \n",
    "            end = max(end, a) + t \n",
    "            ans += t \n",
    "        return ans / len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n=len(customers)\n",
    "        total=0\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            arrival, time=customers[i]\n",
    "            cur=max(arrival+time,cur+time)\n",
    "            total+=cur-arrival\n",
    "        return total/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        cnt = ans = 0\n",
    "        t = 0\n",
    "        for a,b in customers:\n",
    "            cnt += 1\n",
    "            if a >= t:\n",
    "                t = a + b\n",
    "                ans += b\n",
    "            else:\n",
    "                t += b\n",
    "                ans += t - a\n",
    "        return ans / cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        cur1=0\n",
    "        cur2=0\n",
    "        for i in customers:\n",
    "            if i[0]>=cur2:\n",
    "                cur1+=i[1]\n",
    "                cur2=i[0]+i[1]\n",
    "            else:\n",
    "                cur1+=cur2-i[0]+i[1]\n",
    "                cur2+=i[1]\n",
    "        return cur1/len(customers)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        wait = []\n",
    "        target = 0\n",
    "        for i in customers:\n",
    "            if i[0] >= target:\n",
    "                wait.append(i[1])\n",
    "                target = i[0] + i[1]\n",
    "            else:\n",
    "                wait.append(target - i[0] + i[1])\n",
    "                target += i[1]\n",
    "        return sum(wait) / len(customers)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        wait_sum = 0    #等待的时间，总和\n",
    "        chef = 0    #厨师闲的时刻，可以做菜的时刻\n",
    "        for arrive, cost in customers:\n",
    "            if chef <= arrive:  #客人到之前，厨师就是闲着的，立马可以开始\n",
    "                chef = arrive\n",
    "                chef += cost    #厨师做完这道菜，才可以闲\n",
    "                wait_sum += cost\n",
    "            else:               #厨师还在忙\n",
    "                chef += cost        #厨师忙完了，立马给当前这位客人做饭\n",
    "                wait_sum += (chef - arrive) #这位客人等待的时间\n",
    "\n",
    "        return wait_sum / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        res = customers[0][1]\n",
    "\n",
    "        max_ = sum(customers[0])\n",
    "\n",
    "        for i in range(1, len(customers)):\n",
    "            arr, time = customers[i]\n",
    "            if arr <= max_:\n",
    "                max_ += time \n",
    "                res += max_ - arr\n",
    "            else:\n",
    "                max_ = arr + time\n",
    "                res += time\n",
    "\n",
    "        \n",
    "        return res / len(customers)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        num = len(customers)\n",
    "        wait = 0\n",
    "        cur = customers[0][0]\n",
    "        for customer in customers:\n",
    "            wait += max(cur-customer[0], 0) + customer[1]\n",
    "            cur = max(cur+customer[1], customer[0]+customer[1])\n",
    "            \n",
    "        print(wait)\n",
    "        return float(wait/num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        ans = 0\n",
    "        free = 0  # 厨师开始有空的时间\n",
    "        for start, time in customers:\n",
    "            # 如果来的时候厨师还在忙，就得多等等\n",
    "            if start < free:\n",
    "                ans += free - start\n",
    "            elif start > free:\n",
    "                free = start\n",
    "            free += time\n",
    "            ans += time\n",
    "        return ans / len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        waiting_time = 0\n",
    "        curr_time = 0\n",
    "        for cust in customers:\n",
    "            curr_time = max(curr_time, cust[0]) + cust[1] \n",
    "            t = curr_time - cust[0]\n",
    "            waiting_time += t\n",
    "\n",
    "        return waiting_time / len(customers)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        cur, wait = 0., 0.\n",
    "        for x, y in customers:\n",
    "            cur = max(cur, x)\n",
    "            wait += cur + y - x\n",
    "            cur = cur + y\n",
    "        return wait / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        return (a:=0)+(b:=0)*len([(b := max(b, i[0])+i[1])+(a := a+b-i[0]) for i in customers])+a/len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        cur, wait = 0, 0\n",
    "        for x, y in customers:\n",
    "            cur = max(cur, x) + y\n",
    "            wait += cur - x\n",
    "        return wait*1. / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 模拟\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        ans = 0\n",
    "        cur = customers[0][0]\n",
    "        for a, w in customers:\n",
    "            if a < cur:\n",
    "                ans += cur - a\n",
    "            else:\n",
    "                cur = a\n",
    "\n",
    "            ans += w\n",
    "            cur += w\n",
    "\n",
    "        return ans / len(customers)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        pre_done_time = 0\n",
    "        ex_wait_time = 0\n",
    "        wait_time = 0\n",
    "        for cus in customers:\n",
    "            if cus[0] >= pre_done_time:\n",
    "                ex_wait_time = 0\n",
    "                pre_done_time = cus[0] + cus[1]\n",
    "            else:\n",
    "                ex_wait_time = pre_done_time - cus[0]\n",
    "                pre_done_time = pre_done_time + cus[1]\n",
    "            wait_time += ex_wait_time + cus[1]\n",
    "        return wait_time/len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        sum_time = 0\n",
    "        cur_time = customers[0][0]\n",
    "        for i in range(len(customers)):\n",
    "            sum_time += customers[i][1]\n",
    "            sum_time += max(cur_time - customers[i][0], 0)\n",
    "            cur_time = max(cur_time, customers[i][0]) + customers[i][1]\n",
    "        return round(sum_time / len(customers), 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        dish_time = 0 #做完菜的时间\n",
    "        wait_time = 0 # 顾客等待时间之和\n",
    "    \n",
    "        for (arrive,make) in customers:\n",
    "            if arrive>=dish_time:\n",
    "                dish_time = arrive\n",
    "            dish_time = dish_time + make\n",
    "            wait_time += dish_time-arrive\n",
    "            \n",
    "        return wait_time/len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        cus_num = len(customers)\n",
    "        arrive_time = []\n",
    "        consume_time = []\n",
    "        for i in range(cus_num):\n",
    "            arrive_time.append(customers[i][0])\n",
    "            consume_time.append(customers[i][1])\n",
    "        waiting_time = consume_time[0]\n",
    "        finish_time = arrive_time[0]+consume_time[0]\n",
    "        for j in range(1, cus_num):\n",
    "            if arrive_time[j] >= finish_time:\n",
    "                finish_time = arrive_time[j] + consume_time[j]\n",
    "                waiting_time += consume_time[j]\n",
    "            else:\n",
    "                waiting_time += finish_time-arrive_time[j]+consume_time[j]\n",
    "                finish_time = finish_time + consume_time[j]\n",
    "        return waiting_time/cus_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i in customers:\n",
    "            if cur > i[0]:\n",
    "                ans += cur - i[0] + i[1]\n",
    "                cur += i[1]\n",
    "            else:\n",
    "                ans += i[1]\n",
    "                cur = i[0] + i[1]\n",
    "        return ans/len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            start = customers[i][0]\n",
    "            end = customers[i][1]\n",
    "            if i == 0:\n",
    "                pre = start + end\n",
    "                t = pre - start\n",
    "            else:\n",
    "                tmp = max(pre, start) + end\n",
    "                t = tmp - start\n",
    "                pre = tmp\n",
    "            ans.append(t)\n",
    "        return sum(ans) / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        waitTime = 0\n",
    "        time = 0\n",
    "        for i in range(len(customers)):\n",
    "            time = max(customers[i][0], time)\n",
    "            time += customers[i][1]\n",
    "            waitTime += time - customers[i][0]\n",
    "        return waitTime / len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n=len(customers)\n",
    "        total=0\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            arrival, time=customers[i]\n",
    "            if cur<=arrival:\n",
    "                total+=time\n",
    "                cur=arrival+time\n",
    "            else:\n",
    "                cur+=time\n",
    "                total+=cur-arrival\n",
    "        return total/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        time=customers[0][0]\n",
    "        wait=0\n",
    "        for i,j in customers:\n",
    "            wait+=max(time-i,0)+j\n",
    "            time=max(time,i)+j\n",
    "        return wait/len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        last_time = 0\n",
    "        total_time = 0\n",
    "        for arrival, time in customers:\n",
    "            if(arrival <= last_time):\n",
    "                last_time += time\n",
    "            else:\n",
    "                last_time = arrival + time \n",
    "            total_time += last_time - arrival\n",
    "        return total_time / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        wait_sum = 0    #等待的时间，总和\n",
    "        chef = 0    #厨师闲的时刻，可以做菜的时刻\n",
    "        for arrive, cost in customers:\n",
    "            if chef <= arrive:  #客人到之前，厨师就是闲着的，立马可以开始\n",
    "                chef = arrive\n",
    "                chef += cost    #厨师做完这道菜，才可以闲\n",
    "                wait_sum += cost\n",
    "            else:               #厨师还在忙\n",
    "                chef += cost        #厨师忙完了，立马给当前这位客人做饭\n",
    "                wait_sum += (chef - arrive) #这位客人等待的时间\n",
    "\n",
    "        return wait_sum / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        dish_time = 0 #做完菜的时间\n",
    "        wait_time = 0 # 顾客等待时间之和\n",
    "        start_time = 0\n",
    "        for (arrive,make) in customers:\n",
    "            if arrive>=start_time:\n",
    "                start_time = arrive\n",
    "            dish_time = start_time + make\n",
    "            wait_time += dish_time-arrive\n",
    "            start_time = dish_time\n",
    "        return wait_time/len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        time = 0\n",
    "        cnt = 0\n",
    "        for start, duration in customers:\n",
    "            time = max(time - start, 0) + start + duration\n",
    "            cnt += time - start\n",
    "        return cnt / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "\n",
    "        worktime=0\n",
    "        waittime=0\n",
    "        for a,r in customers:\n",
    "            if a>=worktime:\n",
    "                worktime=a+r\n",
    "                waittime+=r\n",
    "            else:\n",
    "                worktime+=r\n",
    "                waittime+=worktime-a\n",
    "            #print(waittime)\n",
    "        n=len(customers)\n",
    "\n",
    "        return waittime/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        cur = 0\n",
    "        wait = [0] * len(customers)\n",
    "        for i in range(len(customers)):\n",
    "            wait[i] = customers[i][1] + max(cur - customers[i][0], 0)\n",
    "            cur = customers[i][1] + max(cur, customers[i][0])\n",
    "        return sum(wait) / len(wait)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        cur, wait = 0, 0\n",
    "        for x, y in customers:\n",
    "            cur = max(cur, x) + y\n",
    "            wait += cur - x\n",
    "        return wait*1. / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        start = 0\n",
    "        tot = 0\n",
    "        for a, t in customers:\n",
    "            start = max(start, a) + t\n",
    "            tot += start - a \n",
    "        return tot / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        n = len(customers)\n",
    "        cur, wait = 0., 0.\n",
    "        for x, y in customers:\n",
    "            cur = max(cur, x)\n",
    "            wait += cur + y - x\n",
    "            cur = cur + y\n",
    "        return wait / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        time=0\n",
    "        n=len(customers)\n",
    "        first=customers[0]\n",
    "        cooker=first[0]\n",
    "        for i,c in enumerate(customers):\n",
    "            if cooker<c[0]:\n",
    "                cooker=c[0]\n",
    "            c_start=c[0]\n",
    "            time+=cooker+c[1]-c_start\n",
    "            cooker+=c[1]\n",
    "        \n",
    "        return time/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        wait_sum = 0    #等待的时间，总和\n",
    "        chef = 0    #厨师闲的时刻，可以做菜的时刻\n",
    "        for arrive, cost in customers:\n",
    "            if chef <= arrive:  #客人到之前，厨师就是闲着的，立马可以开始\n",
    "                chef = arrive\n",
    "                chef += cost    #厨师做完这道菜，才可以闲\n",
    "                wait_sum += cost\n",
    "            else:               #厨师还在忙\n",
    "                chef += cost        #厨师忙完了，立马给当前这位客人做饭\n",
    "                wait_sum += (chef - arrive) #这位客人等待的时间\n",
    "\n",
    "        return wait_sum / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        starts = [customers[0][0]]\n",
    "        for arr0, arr1 in pairwise(customers):\n",
    "            starts.append(max(starts[-1] + arr0[1], arr1[0]))\n",
    "        # print(starts)\n",
    "        ans = 0\n",
    "        for [arr, time], start in zip(customers, starts):\n",
    "            ans += time + max(0, start - arr)\n",
    "        return ans/(len(customers))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        start = 0\n",
    "\n",
    "        waits = 0\n",
    "        for a, t in customers:\n",
    "            if start < a:\n",
    "                waits += t\n",
    "                start = a + t\n",
    "            else:\n",
    "                waits += (start + t) - a\n",
    "                start = start + t\n",
    "\n",
    "        return waits / len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        start = 0\n",
    "        waitTime = 0\n",
    "        for customer in customers:\n",
    "            start = max(start, customer[0])\n",
    "            waitTime += start - customer[0] + customer[1]\n",
    "            start += customer[1]\n",
    "        return waitTime / len(customers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        waitTime = 0\n",
    "        time = 0\n",
    "        for i in range(len(customers)):\n",
    "            if time <= customers[i][0]:\n",
    "                time = customers[i][0] + customers[i][1]\n",
    "                waitTime += customers[i][1]\n",
    "            else:\n",
    "                time += customers[i][1]\n",
    "                waitTime += time - customers[i][0]\n",
    "        return waitTime / len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        ans=0\n",
    "        num=0\n",
    "        n=len(customers)\n",
    "        for i in customers:\n",
    "            if num<=i[0]:\n",
    "                ans+=i[1]\n",
    "                num=i[0]+i[1]\n",
    "            else:\n",
    "                num+=i[1]\n",
    "                ans+=num-i[0]\n",
    "        return ans/n\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        start = 0\n",
    "        sm = 0\n",
    "        for a, t in customers:\n",
    "            start = max(a, start) + t \n",
    "            sm += start - a \n",
    "        return sm / len(customers)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageWaitingTime(self, customers: List[List[int]]) -> float:\n",
    "        start, end = 0, 0\n",
    "        arr = []\n",
    "        for i in range(len(customers)):\n",
    "            if customers[i][0] > end:\n",
    "                start = customers[i][0]\n",
    "                end = start + customers[i][1]\n",
    "                arr.append(customers[i][1])\n",
    "            else:\n",
    "                start = customers[i][0]\n",
    "                end = end + customers[i][1]\n",
    "                arr.append(end-start)\n",
    "        return (sum(arr)/len(arr))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
